class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sz = nums.size(), Min = INT_MAX, sum = 0, m = 0; // m统计0和负数
        sort(nums.begin(), nums.end());
        for(int i = 0; i < sz; ++i)
        {
            sum += nums[i];
            Min = min(Min, abs(nums[i])); // 绝对值最小的数
            if(nums[i] <= 0)
                ++m;
        }
        if(m >= k)
        {
            for(int i = 0; i < k; ++i)
                sum -= 2 * nums[i]; // 最小的负数变正数，两倍
        }
        else // m < k
        {
            for(int i = 0; i < m; ++i) // 先把所有的负数变成正数
                sum -= 2 * nums[i];
            if((k - m) % 2 == 1) // 绝对值最小的数取反
                sum += 2 * -Min;
        }
        return sum;
    }
};